van Emde Boas Tree Algorithm

A van Emde Boas tree (Dutch pronunciation: [ vɑn' ɛmdə' boːɑs ]), also known as a vEB tree or van Emde Boas priority queue, is a tree data structure which implements an associative array with M-bit integer keys. It was invented by a team led by Dutch computer scientist Peter van Emde Boas in 1975.
/*
 Petar 'PetarV' Velickovic
 Data Structure: van Emde Boas Tree (vEB)
*/

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>
using namespace std;
typedef long long lld;
typedef unsigned long long llu;

/*
 van Emde Boas Tree structure for holding a set of integers in a given universe.
 Complexity:    O(1) for min, max and first
                O(log log u) for member, insert, delete, pred, succ, extractMin and decreaseKey
*/

class vEB
{
    llu u;
    
    llu *m, *M;
    vEB *summary;   // used if u != 2
    vEB **cluster;  // used if u != 2
    
public:
    vEB(llu);
    
    bool member(llu);
    void insert(llu);
    void Delete(llu);
    llu min();
    llu max();
    llu* pred(llu);
    llu* succ(llu);
    
    llu extractMin();
    llu first();
    void decreaseKey(llu, llu);
};

vEB::vEB(llu u)
{
    this -> u = u;
    this -> m = NULL;
    this -> M = NULL;
    
    if (u == 2)
    {
        this -> summary = NULL;
        this -> cluster = NULL;
    }
    
    else
    {
        llu subSize = (llu)sqrt(u);
        this -> summary = new vEB(subSize);
        this -> cluster = new vEB*[subSize];
    }
}

bool vEB::member(llu x)
{
    if (u == 2)
    {
        if (m == NULL) return false;
        if (x == 0) return ((*m) == 0);
        else if (x == 1) return ((*M) == 1);
        return false;
    }
    else
    {
        if (m == NULL) return false;
        if (x < (*m) || x > (*M)) return false;
        else if (x == (*m) || (x == (*M))) return true;
        else
        {
            llu subSize = (llu)sqrt(u);
            llu hi = x / subSize, lo = x % subSize;
            if (cluster[hi] == NULL) return false;
            else return cluster[hi] -> member(lo);
        }

    }
}

void vEB::insert(llu x)
{
    if (u == 2)
    {
        if (x == 0)
        {
            if (m == NULL)
            {
                m = new llu;
                M = new llu;
                (*m) = (*M) = x;
            }
            else (*m) = x;
        }
        else if (x == 1)
        {
            if (M == NULL)
            {
                m = new llu;
                M = new llu;
                (*m) = (*M) = x;
            }
            else (*M) = x;
        }
    }
    else
    {
        if (m == NULL)
        {
            m = new llu;
            M = new llu;
            (*m) = (*M) = x;
        }
        else
        {
            if (x < (*m))
            {
                llu currMin = (*m);
                (*m) = x;
                this -> insert(currMin);
            }
            else
            {
                llu subSize = (llu)sqrt(u);
                llu hi = x / subSize, lo = x % subSize;
                if (cluster[hi] == NULL)
                {
                    cluster[hi] = new vEB(subSize);
                    cluster[hi] -> insert(lo);
                    summary -> insert(hi);
                }
                else cluster[hi] -> insert(lo);
                
                if (x > (*M)) (*M) = x;
            }
        }
    }
}

void vEB::Delete(llu x)
{
    if (u == 2)
    {
        if (x == 0)
        {
            if ((*M) == 0)
            {
                m = M = NULL;
            }
            else (*m) = 1;
        }
        else if (x == 1)
        {
            if ((*m) == 1)
            {
                m = M = NULL;
            }
            else (*M) = 0;
        }
    }
    else
    {
        llu subSize = (llu)sqrt(u);
        llu hi = x / subSize, lo = x % subSize;
        
        if (x == (*m))
        {
            if (x == (*M))
            {
                m = M = NULL;
            }
            else
            {
                llu nextMinHi = summary -> min();
                llu nextMinLo = cluster[summary -> min()] -> min();
                llu nextMin = nextMinHi * subSize + nextMinLo;
                this -> Delete(nextMin);
                (*m) = nextMin;
            }
        }
        else
        {
            cluster[hi] -> Delete(lo);
            if (cluster[hi] -> m == NULL)
            {
                summary -> Delete(hi);
                delete cluster[hi];
                cluster[hi] = NULL;
            }
            if (x == (*M))
            {
                if (summary -> m == NULL) (*M) = (*m);
                else
                {
                    llu nextMaxHi = summary -> max();
                    llu nextMaxLo = cluster[summary -> max()] -> max();
                    (*M) = nextMaxHi * subSize + nextMaxLo;
                }
            }
        }
    }
}

llu vEB::min()
{
    return (*m);
}

llu vEB::max()
{
    return (*M);
}

llu* vEB::pred(llu x)
{
    if (u == 2)
    {
        if (x == 0) return NULL;
        else if (x == 1)
        {
            if (m == NULL) return NULL;
            if ((*m) == 1) return NULL;
            return m;
        }
        else return NULL;
    }
    else
    {
        if (m == NULL) return NULL;
        if (x <= (*m)) return NULL;
        if (x > (*M)) return M;
        llu subSize = (llu)sqrt(u);
        llu hi = x / subSize;
        llu lo = x % subSize;
        if (cluster[hi] == NULL)
        {
            llu* prev = summary -> pred(hi);
            llu* ret = new llu;
            (*ret) = (*prev) * subSize + cluster[(*prev)] -> max();
            return ret;
        }
        else
        {
            llu *newLo, *newHi;
            newHi = new llu;
            newLo = new llu;
            (*newHi) = hi;
            llu minInCluster = cluster[hi] -> min();
            if (lo > minInCluster) newLo = cluster[hi] -> pred(lo);
            else
            {
                newHi = summary -> pred(hi);
                (*newLo) = cluster[(*newHi)] -> max();
            }
            llu *ret = new llu;
            (*ret) = (*newHi) * subSize + (*newLo);
            return ret;
        }
    }
}

llu* vEB::succ(llu x)
{
    if (u == 2)
    {
        if (x == 1) return NULL;
        else if (x == 0)
        {
            if (M == NULL) return NULL;
            if ((*M) == 0) return NULL;
            return M;
        }
        else return NULL;
    }
    else
    {
        if (m == NULL) return NULL;
        if (x >= (*M)) return NULL;
        if (x < (*m)) return m;
        llu subSize = (llu)sqrt(u);
        llu hi = x / subSize;
        llu lo = x % subSize;
        if (cluster[hi] == NULL)
        {
            llu* next = summary -> succ(hi);
            llu* ret = new llu;
            (*ret) = (*next) * subSize + cluster[(*next)] -> min();
            return ret;
        }
        else
        {
            llu *newLo, *newHi;
            newHi = new llu;
            newLo = new llu;
            (*newHi) = hi;
            llu maxInCluster = cluster[hi] -> max();
            if (lo < maxInCluster) newLo = cluster[hi] -> succ(lo);
            else
            {
                newHi = summary -> succ(hi);
                (*newLo) = cluster[(*newHi)] -> min();
            }
            llu *ret = new llu;
            (*ret) = (*newHi) * subSize + (*newLo);
            return ret;
        }
    }
}

llu vEB::extractMin()
{
    llu ret = this -> min();
    this -> Delete(ret);
    return ret;
}

llu vEB::first()
{
    return this -> min();
}

void vEB::decreaseKey(llu x, llu y)
{
    // Preconditions: y < x, x is in the tree, y is not in the tree
    
    this -> Delete(x);
    this -> insert(y);
}

int main()
{
    vEB *vEB = new class vEB(16);
    
    vEB -> insert(2);
    vEB -> insert(3);
    vEB -> insert(4);
    vEB -> insert(5);
    vEB -> insert(7);
    vEB -> insert(14);
    vEB -> insert(15);
    
    printf("%llu\n", vEB -> min());
    printf("%llu\n", vEB -> max());
    printf("%llu\n", (*vEB -> pred(9)));
    printf("%llu\n", (*vEB -> succ(9)));
    
    vEB -> Delete(7);
    vEB -> Delete(14);
    
    
    printf("%llu\n", (*vEB -> pred(9)));
    printf("%llu\n", (*vEB -> succ(9)));
    
    return 0;
}

LANGUAGE:

DARK MODE: